//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//子数组是数组中的一个连续部分。

//示例 1：
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
//示例 2：
//输入：nums = [1]
//输出：1
//示例 3：
//输入：nums = [5,4,-1,7,8]
//输出：23

//1 <= nums.length <= 105
//-104 <= nums[i] <= 104

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if (len == 1) return nums[0];
        vector<int> sum(len, 0);
        vector<int> max_sum_r(len, 0);
        sum[0]= nums[0];
        int ans=nums[0];
        int max_sum = nums[0];
        for(int i=1; i<len; ++i){
            sum[i] = sum[i-1]+nums[i];
            if(nums[i]>ans) ans =nums[i];
            if(sum[i]>max_sum) max_sum = sum[i];
        }

        int max_sum_rr=sum[len-1];
        max_sum_r[len-1] = max_sum_rr;
        for(int i=len-2;i>=0;--i){
            if(sum[i]> max_sum_rr)  {
                max_sum_rr = sum[i];
            }
            max_sum_r[i] = max_sum_rr;
        }

        for(int i=0;i<len-1;++i){
            ans = max(ans, max_sum_r[i+1]-sum[i]);
        }

        return max(ans, max_sum);
    }
};

int main() {
//    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
//    vector<int> nums={5,4,-1,7,8};
//    vector<int> nums={1, 1, -2};
    vector<int> nums={9,0,-2,-2,-3,-4,0,1,-4,5,-8,7,-3,7,-6,-4,-7,-8};
    Solution solution;
    int ans = solution.maxSubArray(nums);
    std::cout << "ans = " <<ans<< std::endl;
    return 0;
}
